package com.zp.self.module.level_4_算法练习.算法.双指针.左右指针;

/**
 * @author By ZengPeng
 */
public class 力扣_5_最长回文子串 {
    //测试
    public static void main(String[] args) {

//        System.out.println(new 力扣_5_最长回文子串().longestPalindrome("abcd"));
//        System.out.println(new 力扣_5_最长回文子串().longestPalindrome("babad"));
//        System.out.println(new 力扣_5_最长回文子串().longestPalindrome("cbbd"));
        System.out.println(new 力扣_5_最长回文子串().longestPalindrome("aaaa"));
        System.out.println(new 力扣_5_最长回文子串().longestPalindrome("ccc"));
        System.out.println(new 力扣_5_最长回文子串().longestPalindrome("acc"));
    }

    /**
    题目：给你一个字符串 s，找到 s 中最长的回文子串。

     示例 1：
     输入：s = "babad"
     输出："bab"
     解释："aba" 同样是符合题意的答案。

     示例 2：
     输入：s = "cbbd"
     输出："bb"

    分析：【P 💜💜💜】
       1.滑动窗口:   以当前遍历的节点向左右出发遍历，左右字符不相等结束.记录当前最大长度
                    考虑两种情况：1.起点[left=i-1, right=i] ，2.起点[left=i-1, right=i+1]
                                    至于：[left=i, right=i+1]  ，不就等于下一位的情况1吗？(i-1)+1 ,(i)+1   --> [left=i, right=i+1] ,所以不考虑
                    --执行用时：12 ms, 在所有 Java 提交中击败了91.05%的用户

    边界值 & 注意点：
       1."ccc"
       2."aaaa"
       3."ac"
       4."a"
       5."cbbd"
    **/

    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int maxLength =1;
        String res = String.valueOf(chars,0,1);
        for (int index = 1; index < chars.length; index++) {
            String currentStr =  palindromeStringLenth(chars, index - 1, index,maxLength);//1.起点[left=i-1, right=i]
            if(currentStr!=null){
                res=currentStr;maxLength=currentStr.length();
            }
            currentStr =  palindromeStringLenth(chars, index - 1, index+1,maxLength);//2.起点[left=i-1, right=i+1]
            if(currentStr!=null){
                res=currentStr;maxLength=currentStr.length();
            }
        }
        return res;
    }
    private String palindromeStringLenth(char[] chars, int left, int right, int maxLength) {
        while (left>-1 && right<chars.length){
            if(chars[left]!=chars[right])
               break;
            left--;right++;
        }
        if( (right-left-1)>maxLength)
            return String.valueOf(chars,++left,right-left);
        else
            return null;
    }




    // --------------------------------------- old --------------------------
    public String longestPalindrome_oldMe(String s) {
        int currentMax = 1;
        String str =s.substring(0,1);
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                str = getMaxString(s,currentMax,i - 1,i,str);//i == i-1
                currentMax = str.length();
            }
            if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
                str =  getMaxString(s,currentMax,i ,i + 1,str);//i == i+1
                currentMax = str.length();
            }
            if(i+1<s.length() && s.charAt(i-1)==s.charAt(i+1)){
                str = getMaxString(s, currentMax, i - 1, i + 1,str);////以i为中心的对称点
                currentMax = str.length();
            }
        }
        return str;
    }

    public String  getMaxString(String s, int currentMax, int left, int right, String str){
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) == s.charAt(right)) {
                if (right - left + 1 > currentMax) {
                    currentMax = right - left + 1;
                    str = s.substring(left, right + 1);
                }
            } else break;
            left--;
            right++;
        }
        return str;
    }
}
